1. Technical Field
This relates to the design and manufacture of very large scale integrated (xe2x80x9cVLSIxe2x80x9d) circuits and, more particularly, to an active region management technique suitable for use in conjunction with the design and manufacture of VLSI circuits.
2. Description of the Relevant Art
A VLSI circuit is typically composed of a plurality of layers, each having a plurality of generally rectangular shaped components positioned thereon, oriented in either the horizontal or vertical axis. VLSI circuit designers commonly refer to these generally rectangular shaped components as xe2x80x9ccomponent tilesxe2x80x9d and to the generally rectangular shaped open spaces that surround the component tiles as xe2x80x9cspace tiles.xe2x80x9d Component tiles that are to be connected on a VLSI circuit are said to form a xe2x80x9cnetxe2x80x9d, while any component tile not connected to a particular net is considered to be an obstruction to that net. Two tiles are said to be xe2x80x9cadjacentxe2x80x9d if they touch along their edges and xe2x80x9coverlappingxe2x80x9d if there is even a single point located within the interior of both tiles. A set of tiles positioned within a routing area is said to be xe2x80x9cmaximalxe2x80x9d if no two tiles are either overlapping or adjacent on their left or right edges.
One step in the design of a VLSI circuit is to select the wire paths that extend through the space tiles to connect the electrically equivalent component tiles that form nets. A current technique used to determine these paths utilizes a tile expansion algorithm. More specifically, clear space around the component tiles forming a net is fractured into maximal space tiles. Adjoining ones of these maximal space tiles are used to define the most efficient tile path between two components. The path of the actual connection between the components, known as the wire path, is then defined as the route through the space tile path from the component source tile to the component destination tile.
The aforementioned technique for selecting the wire paths for a VLSI circuit design suffers from two drawbacks, both of which may add to the cost of VLSI circuits manufactured in accordance with the design. First, if defined in accordance with the above-described manner, a tile path is not necessarily the optimal tile path through the clear space. Second, since the width of a tile path is typically much larger than the width of a wire path, multiple wire paths may exist through a given tile path. If the wire path located within the tile path is arbitrarily selected, the selected wire path is not necessarily the most efficient wire path potentially located within the tile path.
Disclosed herein is a method and associated apparatus for determining an active region for a routing area having a plurality of components, each having a lower edge, an upper edge and a horizontal span, positioned thereon. A set of sweep lines, each extending along an upper or lower edge of at least one of the plurality of components, are determined for the routing area. A component tile density is determined along each one of the set of sweep lines. An active region for the routing area may then be generated from the component tile density along each one of the set of sweep lines. In determine component tile density along a sweep line, the component tile density is incremented by a pre-selected value for the horizontal span of a component tile upon encountering a lower edge thereof and decremented by the pre-selected value for the horizontal span of a component tile upon encountering an upper edge thereof.
The set of sweep lines may be arranged in an ascending order relative to an axis of the routing area and the component tile density determined, for the set of sweep lines, in the ascending order thereof. The first sweep line of the set of sweep lines is aligned with a lower edge of the routing area. For the first sweep line, the component tile density is set to zero at a first side edge of the routing area. A sweep is performed across the routing area and, for each lower edge or interior of a component tile encountered, the component tile density is incremented by the pre-selected value. For the next sweep line in the ascending order, the component tile density is initially set to that determined for the prior sweep line and subsequently adjusted for each lower or upper edge of a component tile encountered. Finally, for the uppermost sweep line in the ascending order, the component tile density is initially set to that determined for the prior sweep line and subsequently adjusted for each lower edge, interior or upper edge of a component tile encountered.